/**
 * 题目：反转链表
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 *
 * https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/description/
 */
public class ReverseListP {
    public ListNode reverseList(ListNode head) {
        return reverse(head);
    }

    private ListNode reverse(ListNode cur) {
        if (cur == null || cur.next == null) {
            return cur;
        }

        ListNode newHead = reverse(cur.next);
        // 反向连接
        cur.next.next = cur;
        // 断开正向连接
        cur.next = null;

        return newHead;
    }
}
